<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <link rel="stylesheet" type="text/css" href="html.css" />
    <title>JAS - Algorithms for Computer Algebra book</title>
  </head>
  <body class="main">
    <h1>Algorithms for Computer Algebra book and JAS methods</h1>

<p>
Summary of algorithms from the 
<a href="http://www.springer.com/computer/theoretical+computer+science/book/978-0-7923-9259-0" 
target="gbb">Algorithms for Computer Algebra</a> 
book and corresponding JAS classes and methods.
</p>


<h2>Algorithms for Computer Algebra book</h2>

<p>
The JAS base package <code>edu.jas</code> name is omitted in the
following table.
JAS also contains improved versions of the algorithms which may be located through the links.
A short explanation of code organization with interfaces and several implementing classes
can be found in the <a href="design.html">API guide</a>.
</p>

<table border="1" cellpadding="3" summary="Algo CA book to JAS summary" >
<tr>
<td>Algorithms&nbsp;for&nbsp;Computer&nbsp;Algebra</td>
<td>JAS interfaces, classes and methods</td>
<td>remarks</td>
</tr>

<tr>
<td>2.1&nbsp;Euclidean Algorithm, <code>Euclid</code></td>
<td><a href="doc/api/edu/jas/structure/RingElem.html#gcd(C)" target="classFrame"><code>structure.RingElem.gcd</code></a>
</td>
<td>all classes which implement this interface
</td>
</tr>
<tr>
<td>2.2&nbsp;Extended Euclidean Algorithm, <code>EEA</code></td>
<td><a href="doc/api/edu/jas/structure/RingElem.html#egcd(C)" target="classFrame"><code>structure.RingElem.egcd</code></a>
</td>
<td>all classes which implement this interface
</td>
</tr>

<tr>
<td>2.3&nbsp;Primitive Euclidean Algorithm, <code>PrimitiveEuclidean</code></td>
<td><a href="doc/api/edu/jas/ufd/GreatestCommonDivisorPrimitive.html" target="classFrame"><code>ufd.GreatestCommonDivisorPrimitive</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>4.1&nbsp;Multiprecision Integer Multiplication, <code>BigIntegerMultiply</code></td>
<td><a href="doc/api/edu/jas/arith/BigInteger.html#multiply(edu.jas.arith.BigInteger)" target="classFrame"><code>BigInteger.multiply</code></a>
</td>
<td>adapter for native Java implementation in <code>java.math.BigInteger.multiply</code>
</td>
</tr>

<tr>
<td>4.2&nbsp;Karatsuba's Multiplication Algorithm, <code>Karatsuba</code></td>
<td><a href="doc/api/edu/jas/arith/" target="classFrame"><code></code></a>
</td>
<td>not visible
</td>
</tr>

<tr>
<td>4.3&nbsp;Polynomial Trial Division Algorithm, <code>TrialDivision</code></td>
<td>not implemented 
</td>
<td>see 
<a href="doc/api/edu/jas/poly/GenPolynomial.html#divide(edu.jas.poly.GenPolynomial)" target="classFrame"><code>GenPolynomial.divide</code></a>
and 
<a href="doc/api/edu/jas/poly/PolyUtil.html#basePseudoDivide(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>PolyUtil.basePseudoDivide</code></a>
</td>
</tr>

<tr>
<td>4.4&nbsp;Fast Fourier Transform, <code>FFT</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>4.5&nbsp;Fast Fourier Polynomial Multiplication, <code>FFT_Multiply</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>4.6&nbsp;Newtons's Method for Power Series Inversion, <code>FastNewtonInversion</code></td>
<td>not implemented
</td>
<td>see
<a href="doc/api/edu/jas/ps/UnivPowerSeries.html#inverse()" target="classFrame"><code>UnivPowerSeries.inverse()</code></a>
and
<a href="doc/api/edu/jas/ps/MultiVarPowerSeries.html#inverse()" target="classFrame"><code>MultiVarPowerSeries.inverse()</code></a>
</td>
</tr>

<tr>
<td>4.7&nbsp;Newtons's Method for Solving P(y) = 0, <code>NewtonSolve</code></td>
<td>not implemented
</td>
<td>see
<a href="doc/api/edu/jas/ps/UnivPowerSeriesRing.html#solveODE(edu.jas.ps.UnivPowerSeries,%20C)" target="classFrame"><code>UnivPowerSeriesRing.solveODE()</code></a>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>5.1&nbsp;Garner's Chinese Remainder Algorithm, <code>IntegerCRA</code></td>
<td><a href="doc/api/edu/jas/arith/ModIntegerRing.html#chineseRemainder(edu.jas.arith.ModInteger,%20edu.jas.arith.ModInteger,%20edu.jas.arith.ModInteger)" target="classFrame"><code>ModIntegerRing.chineseRemainder()</code></a>
</td>
<td>only for two moduli
</td>
</tr>

<tr>
<td>5.2&nbsp;Newtons Interpolation Algorithm, <code>NewtonInterp</code></td>
<td>not implemented 
</td>
<td>see 
<a href="doc/api/edu/jas/poly/PolyUtil.html#chineseRemainder(edu.jas.poly.GenPolynomialRing,%20edu.jas.poly.GenPolynomial,%20C,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>PolyUtil.chineseRemainder()</code></a>
and
<a href="doc/api/edu/jas/poly/PolyUtil.html#interpolate(edu.jas.poly.GenPolynomialRing,%20edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial,%20C,%20C,%20C)" target="classFrame"><code>PolyUtil.interpolate()</code></a>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>6.1&nbsp;Univariate Hensel Lifting Algorithm, <code>UnivariateHensel</code></td>
<td><a href="doc/api/edu/jas/ufd/HenselUtil.html#liftHensel(edu.jas.poly.GenPolynomial,%20java.util.List,%20long,%20edu.jas.arith.BigInteger)" target="classFrame"><code>HenselUtil.liftHensel()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>6.2&nbsp;Multivariate Polynomial Diophantine Equantions, <code>MultivariateDiophant</code></td>
<td><a href="doc/api/edu/jas/ufd/HenselMultUtil.html#liftDiophant(java.util.List,%20edu.jas.poly.GenPolynomial,%20java.util.List,%20long,%20long)" target="classFrame"><code>HenselMultUtil.liftDiophant()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>6.3&nbsp;Univariate Polynomial Diophantine Equantions, <code>UnivariateDiophant</code></td>
<td><a href="doc/api/edu/jas/ufd/HenselUtil.html#liftDiophant(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial,%20long,%20long)" target="classFrame"><code>HenselUtil.liftDiophant()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>6.4&nbsp;Multivariate Hensel Lifting Algorithm, <code>MultivariateHensel</code></td>
<td><a href="doc/api/edu/jas/ufd/HenselMultUtil.html#liftHensel(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial,%20java.util.List,%20java.util.List,%20long,%20java.util.List)" target="classFrame"><code>HenselMultUtil.liftHensel()</code></a>
<td>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>7.1&nbsp;Modular GCD Algorithm, <code>MGCD</code></td>
<td><a href="doc/api/edu/jas/ufd/GreatestCommonDivisorModular.html#baseGcd(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>GreatestCommonDivisorModular.baseGcd()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>7.2&nbsp;Multivariate GCD Reduction Algorithm, <code>PGCD</code></td>
<td><a href="doc/api/edu/jas/ufd/GreatestCommonDivisorModEval.html#gcd(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>GreatestCommonDivisorModEval.gcd()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td></td>
<td><a href="doc/api/edu/jas/ufd/GreatestCommonDivisorSubres.html#gcd(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>GreatestCommonDivisorSubres.gcd()</code></a>
</td>
<td>many more algorithms, for example using polynomial remainder sequences
  (PRS), in particular a sub-resultant PRS
</td>
</tr>

<tr>
<td>7.3&nbsp;Extended Zassenhaus GCD Algorithm, <code>EZ-GCD</code></td>
<td><a href="doc/api/edu/jas/ufd/GreatestCommonDivisorHensel.html#recursiveUnivariateGcd(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>GreatestCommonDivisorHensel. recursiveUnivariateGcd()</code></a>
</td>
<td>not complete in all cases
</td>
</tr>

<tr>
<td>7.4&nbsp;GCD Heuristic Algorithm, <code>GCDHEU</code></td>
<td>not implemented
</td>
<td>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>8.1&nbsp;Square-Free Factorization, <code>SquareFree</code></td>
<td><a href="doc/api/edu/jas/ufd/SquarefreeFieldChar0.html#squarefreeFactors(edu.jas.poly.GenPolynomial)" target="classFrame"><code>SquarefreeFieldChar0.squarefreeFactors()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>8.2&nbsp;Yun's Square-Free Factorization, <code>SquareFree2</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented 
</td>
<td>
</td>
</tr>

<tr>
<td>8.3&nbsp;Finite Field Square-Free Factorization, <code>SquareFreeFF</code></td>
<td><a href="doc/api/edu/jas/ufd/SquarefreeFiniteFieldCharP.html#squarefreeFactors(edu.jas.poly.GenPolynomial)" target="classFrame"><code>SquarefreeFiniteFieldCharP .squarefreeFactors()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td></td>
<td><a href="doc/api/edu/jas/ufd/SquarefreeInfiniteFieldCharP.html#squarefreeFactors(edu.jas.ufd.Quotient)" target="classFrame"><code>SquarefreeInfiniteFieldCharP .squarefreeFactors()</code></a>
</td>
<td>Algorithm for infinite fields of characteristic p, not in the book.
</td>
</tr>

<tr>
<td>8.4&nbsp;Berlekamp's Factorization Algorithm, <code>Berlekamp</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>8.5&nbsp;Form Q Matrix, <code>FormMatrixQ</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>8.6&nbsp;Null Space Basis Algorithm, <code>NullSpaceBasis</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>8.7&nbsp;Big Prime Berlekamp Factoring Algorithm, <code>BigPrimeBerlekamp</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>8.8&nbsp;Distinct Degree Factorization I, <code>PartialFactorDD</code></td>
<td><a href="doc/api/edu/jas/ufd/FactorModular.html#baseDistinctDegreeFactors(edu.jas.poly.GenPolynomial)" target="classFrame"><code>FactorModular.baseDistinctDegreeFactors()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>8.9&nbsp;Distinct Degree Factorization II, <code>SplitDD</code></td>
<td><a href="doc/api/edu/jas/ufd/FactorModular.html#baseEqualDegreeFactors(edu.jas.poly.GenPolynomial)" target="classFrame"><code>FactorModular.baseEqualDegreeFactors()</code></a>
<td>
</td>
</tr>

<tr>
<td></td>
<td><a href="doc/api/edu/jas/ufd/FactorInteger.html#factorsSquarefree(edu.jas.poly.GenPolynomial)" target="classFrame"><code>FactorInteger.factorsSquarefree()</code></a>
<td>Algorithm of P. Wang, not presented in the book.
</td>
</tr>

<tr>
<td>8.10&nbsp;Factorization over Algebraic Number Fields, <code>AlgebraicFactorization</code></td>
<td><a href="doc/api/edu/jas/ufd/FactorAlgebraic.html#baseFactorsSquarefree(edu.jas.poly.GenPolynomial)" target="classFrame"><code>FactorAlgebraic.baseFactorsSquarefree()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>9.1&nbsp;Fraction-Free Gaussian Elimination, <code>FractionFreeElim</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>but see
<a href="doc/api/edu/jas/gbufd/GroebnerBasePseudoSeq.html#GB(int,%20java.util.List)" target="classFrame"><code>GroebnerBasePseudoSeq.GB()</code></a>
</td>
</tr>

<tr>
<td>9.2&nbsp;Nonlinear Elimination Algorithm, <code>NonlinearElim</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>Based on iterated resultant computations.
See also the characteristic set method
<a href="doc/api/edu/jas/gbufd/CharacteristicSetSimple.html#characteristicSet(java.util.List)" target="classFrame"><code>CharacteristicSetSimple.characteristicSet()</code></a>
</td>
</tr>

<tr>
<td>9.3&nbsp;Solution of Nonlinear System of Equations, <code>NonlinearSolve</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>Based on resultant computations and algebraic root substitution. 
See also the ideal complex and real root computation and decomposition methods
<a href="doc/api/edu/jas/application/PolyUtilApp.html#complexAlgebraicRoots(edu.jas.application.Ideal)" target="classFrame"><code>PolyUtilApp.complexAlgebraicRoots()</code></a>
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>10.1&nbsp;Full Reduction Algorithm, <code>Reduce</code></td>
<td><a href="doc/api/edu/jas/gb/Reduction.html#normalform(java.util.List,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>Reduction.normalform()</code></a>
</td>
<td>all classes which implement this interface
</td>
</tr>

<tr>
<td>10.2&nbsp;Buchbergers's Algorithm for Gr&ouml;bner Bases, <code>Gbasis</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

<tr>
<td>10.3&nbsp;Construction of a Reduced Ideal Basis, <code>ReduceSet</code></td>
<td><a href="doc/api/edu/jas/gb/GroebnerBase.html#minimalGB(java.util.List)" target="classFrame"><code>GroebnerBase.minimalGB()</code></a>
</td>
<td>all classes which implement this interface
</td>
</tr>

<tr>
<td>10.4&nbsp;Improved Construction of a Reduced Gr&ouml;bner Basis, <code>Gbasis</code></td>
<td><a href="doc/api/edu/jas/gb/GroebnerBaseSeq.html#GB(int,%20java.util.List)" target="classFrame"><code>GroebnerBaseSeq.GB()</code></a>
</td>
<td>can be parametrized also with different strategies, e.g. Gebauer &amp; M&ouml;ller
</td>
</tr>

<tr>
<td>10.5&nbsp;Solution of System P in Variable x, <code>Solve1</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#constructUnivariate(int)" target="classFrame"><code>Ideal.constructUnivariate()</code></a>
</td>
<td>univariate polynomials of minimal degree in the ideal
</td>
</tr>

<tr>
<td>10.6&nbsp;Complete Solution of System P, <code>Gr&ouml;bnerSolve</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#zeroDimDecomposition()" target="classFrame"><code>Ideal.zeroDimDecomposition()</code></a>,
</td>
<td>univariate polynomials in the ideal are irreducible
</td>
</tr>

<tr>
<td>10.7&nbsp;Solution of P using Lexicographic Gr&ouml;bner Basis, <code>LexSolve</code></td>
<td><a href="doc/api/edu/jas/application/Ideal.html#zeroDimRootDecomposition()" target="classFrame"><code>Ideal.zeroDimRootDecomposition()</code></a>
</td>
<td>additionally to 10.6, the ideal basis consists of maximally bi-variate polynomials
</td>
</tr>

<tr>
<td colspan="3">&nbsp;</td>
</tr>

<tr>
<td>11.1&nbsp;Hermite's Method for Rational Functions, <code>HermiteReduction</code></td>
<td><a href="doc/api/edu/jas/integrate/ElementaryIntegration.html#integrateHermite(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>ElementaryIntegration.integrateHermite()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>11.2&nbsp;Horowitz's Reduction for Rational Functions, <code>HorowitzReduction</code></td>
<td><a href="doc/api/edu/jas/integrate/ElementaryIntegration.html#integrate(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>ElementaryIntegration.integrate()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>11.3&nbsp;Rothstein/Trager Method, <code>LogarithmicPartIntegral</code></td>
<td><a href="doc/api/edu/jas/integrate/ElementaryIntegration.html#integrateLogPart(edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>ElementaryIntegration.integrateLogPart()</code></a>
</td>
<td>
</td>
</tr>

<tr>
<td>11.4&nbsp;Lazard/Rioboo/Trager Improvement, <code>LogarithmicPartIntegral</code></td>
<td><a href="doc/api/edu/jas/" target="classFrame"><code></code></a>
not implemented
</td>
<td>
</td>
</tr>

</table>

<p>
</p>


<!--
<code></code> 
<p>
</p>
<p>
</p>
<pre>
</pre>
-->

<p><!--a href="README" target="readme" >README</a-->
<!--a href="" target="classFrame"><code></code></a-->
</p>

    <hr />
<address><a href="mailto:kredel at rz.uni-mannheim.de">Heinz Kredel</a></address>
<p>
<!-- Created: Sun May 23 13:14:59 CEST 2010 -->
<!-- hhmts start -->
Last modified: Tue Apr 30 10:16:18 CEST 2013
<!-- hhmts end -->
</p>
<!--p align="right" >
$Id$
</p-->
  </body>
</html>
